{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Shortest Path to Get Food"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getFood"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #获取食物的最短路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你现在很饿，想要尽快找东西吃。你需要找到最短的路径到达一个食物所在的格子。</p>\n",
    "\n",
    "<p>给定一个&nbsp;<code>m x n</code>&nbsp;的字符矩阵&nbsp;<code>grid</code>&nbsp;，包含下列不同类型的格子：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>'*'</code>&nbsp;是你的位置。矩阵中<strong>有且只有一个&nbsp;</strong><code>'*'</code>&nbsp;格子。</li>\n",
    "\t<li><code>'#'</code> 是食物。矩阵中可能存在<strong>多个</strong>食物。</li>\n",
    "\t<li><code>'O'</code>&nbsp;是空地，你可以穿过这些格子。</li>\n",
    "\t<li><code>'X'</code>&nbsp;是障碍，你不可以穿过这些格子。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回你到任意食物的最短路径的长度。如果不存在你到任意食物的路径，返回&nbsp;<code>-1</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>示例 1:</b></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/21/img1.jpg\" style=\"width: 300px; height: 201px;\" />\n",
    "<pre>\n",
    "<b>输入：</b> grid = [[\"X\",\"X\",\"X\",\"X\",\"X\",\"X\"],[\"X\",\"*\",\"O\",\"O\",\"O\",\"X\"],[\"X\",\"O\",\"O\",\"#\",\"O\",\"X\"],[\"X\",\"X\",\"X\",\"X\",\"X\",\"X\"]]\n",
    "<b>输出：</b> 3\n",
    "<b>解释： </b>要拿到食物，你需要走 3 步。</pre>\n",
    "\n",
    "<p><strong>Example 2:</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/21/img2.jpg\" style=\"width: 300px; height: 241px;\" />\n",
    "<pre>\n",
    "<b>输入：</b> grid = [[\"X\",\"X\",\"X\",\"X\",\"X\"],[\"X\",\"*\",\"X\",\"O\",\"X\"],[\"X\",\"O\",\"X\",\"#\",\"X\"],[\"X\",\"X\",\"X\",\"X\",\"X\"]]\n",
    "<b>输出：</b> -1\n",
    "<b>解释：</b> 你不可能拿到食物。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;3:</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/21/img3.jpg\" style=\"width: 300px; height: 188px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> grid = [[\"X\",\"X\",\"X\",\"X\",\"X\",\"X\",\"X\",\"X\"],[\"X\",\"*\",\"O\",\"X\",\"O\",\"#\",\"O\",\"X\"],[\"X\",\"O\",\"O\",\"X\",\"O\",\"O\",\"X\",\"X\"],[\"X\",\"O\",\"O\",\"O\",\"O\",\"#\",\"O\",\"X\"],[\"X\",\"X\",\"X\",\"X\",\"X\",\"X\",\"X\",\"X\"]]\n",
    "<strong>输出:</strong> 6\n",
    "<strong>解释:</strong> 这里有多个食物。拿到下边的食物仅需走 6 步。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>提示：</b></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 200</code></li>\n",
    "\t<li><code>grid[row][col]</code>&nbsp;是&nbsp;<code>'*'</code>、&nbsp;<code>'X'</code>、&nbsp;<code>'O'</code>&nbsp;或&nbsp;<code>'#'</code>&nbsp;。</li>\n",
    "\t<li><code>grid</code>&nbsp;中<strong>有且只有一个</strong>&nbsp;<code>'*'</code>&nbsp;。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shortest-path-to-get-food](https://leetcode.cn/problems/shortest-path-to-get-food/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shortest-path-to-get-food](https://leetcode.cn/problems/shortest-path-to-get-food/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"X\",\"X\",\"X\",\"X\",\"X\",\"X\"],[\"X\",\"*\",\"O\",\"O\",\"O\",\"X\"],[\"X\",\"O\",\"O\",\"#\",\"O\",\"X\"],[\"X\",\"X\",\"X\",\"X\",\"X\",\"X\"]]', '[[\"X\",\"X\",\"X\",\"X\",\"X\"],[\"X\",\"*\",\"X\",\"O\",\"X\"],[\"X\",\"O\",\"X\",\"#\",\"X\"],[\"X\",\"X\",\"X\",\"X\",\"X\"]]', '[[\"X\",\"X\",\"X\",\"X\",\"X\",\"X\",\"X\",\"X\"],[\"X\",\"*\",\"O\",\"X\",\"O\",\"#\",\"O\",\"X\"],[\"X\",\"O\",\"O\",\"X\",\"O\",\"O\",\"X\",\"X\"],[\"X\",\"O\",\"O\",\"O\",\"O\",\"#\",\"O\",\"X\"],[\"X\",\"X\",\"X\",\"X\",\"X\",\"X\",\"X\",\"X\"]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFood(self, grid: List[List[str]]) -> int:\n",
    "        shortest = float(\"inf\")\n",
    "\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "\n",
    "        '''\n",
    "        def dfs(i, j, path):\n",
    "\n",
    "            nonlocal shortest\n",
    "            if grid[i][j] == \"#\":\n",
    "                shortest = min(shortest, path)\n",
    "\n",
    "            grid[i][j] = \"X\"\n",
    "\n",
    "            for dir in dirs:\n",
    "                new_i, new_j = dir[0] + i, dir[1] + j\n",
    "                if 0 <= new_i < m and 0 <= new_j < n and grid[new_i][new_j] != \"X\":\n",
    "                    dfs(new_i, new_j, path + 1)\n",
    "        '''\n",
    "        q = collections.deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == \"*\":\n",
    "                    q.append((i, j))\n",
    "                    break\n",
    "\n",
    "        level = 0\n",
    "        while q:\n",
    "\n",
    "            next_level = []\n",
    "\n",
    "            while q:\n",
    "                x, y = q.popleft()\n",
    "                if grid[x][y] != \"X\":\n",
    "                    if grid[x][y] == \"#\":\n",
    "                        shortest = min(shortest, level)\n",
    "\n",
    "                    grid[x][y] = \"X\"\n",
    "\n",
    "                    for dir in dirs:\n",
    "                        new_i, new_j = dir[0] + x, dir[1] + y\n",
    "                        if 0 <= new_i < m and 0 <= new_j < n and grid[new_i][new_j] != \"X\":\n",
    "                            next_level.append((new_i, new_j))\n",
    "\n",
    "            level += 1\n",
    "\n",
    "            q.extend(next_level)\n",
    "\n",
    "        return shortest if shortest != float(\"inf\") else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFood(self, grid: List[List[str]]) -> int:\n",
    "        from collections import deque\n",
    "        queue = deque()\n",
    "        directions_i = [1, -1, 0, 0]\n",
    "        directions_j = [0, 0, 1, -1]\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == \"*\":\n",
    "                    queue.append((i, j))\n",
    "        distance = 0\n",
    "        while queue:\n",
    "            count = len(queue)\n",
    "            for _ in range(count):\n",
    "                i, j = queue.popleft()\n",
    "                if grid[i][j] == \"#\": return distance\n",
    "                for k in range(4):\n",
    "                    new_i = i + directions_i[k]\n",
    "                    new_j = j + directions_j[k]\n",
    "                    if 0 <= new_i < m and 0 <= new_j < n \\\n",
    "                        and not visited[new_i][new_j] \\\n",
    "                        and grid[new_i][new_j] != \"X\":\n",
    "                        visited[new_i][new_j] = True\n",
    "                        queue.append((new_i, new_j))\n",
    "            distance += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFood(self, grid: List[List[str]]) -> int:\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        que = collections.deque()\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "\n",
    "                if grid[i][j] == \"*\":\n",
    "                    que.append((i,j))\n",
    "                    break\n",
    "            if que:\n",
    "                break\n",
    "\n",
    "        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        res = 0\n",
    "        while que:\n",
    "            res += 1\n",
    "            size = len(que)\n",
    "            for i in range(size):\n",
    "                curx, cury = que.popleft()\n",
    "                for dx, dy in directions:\n",
    "                    nx, ny = curx + dx, cury + dy\n",
    "                    if nx < 0 or nx >= n or ny < 0 or ny >= m or grid[nx][ny] == \"X\":continue\n",
    "                    if grid[nx][ny] == \"#\":\n",
    "                        return res \n",
    "                    que.append((nx, ny))\n",
    "                    grid[nx][ny] = \"X\"\n",
    "\n",
    "        return -1\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFood(self, grid: List[List[str]]) -> int:\n",
    "        m, n = len(grid),len(grid[0])\n",
    "        queue = deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '*':\n",
    "                    queue.append((i,j))\n",
    "                    break\n",
    "            if queue:\n",
    "                break\n",
    "        ans = 0\n",
    "\n",
    "        while queue:  \n",
    "            ans += 1        \n",
    "            for _ in range(len(queue)):\n",
    "                x,y = queue.pop()\n",
    "                for (x_,y_) in [(x+1,y),(x-1,y),(x,y-1),(x,y+1)]:\n",
    "                    if x_ not in range(0,m) or y_ not in range(0,n) or grid[x_][y_] == 'X':\n",
    "                        continue\n",
    "                    if grid[x_][y_] == '#':\n",
    "                        return ans\n",
    "                    grid[x_][y_] = 'X'\n",
    "                    queue.appendleft((x_,y_))\n",
    "                \n",
    "                \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFood(self, grid: List[List[str]]) -> int:\n",
    "\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        que = collections.deque()\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "\n",
    "                if grid[i][j] == \"*\":\n",
    "                    que.append((i,j))\n",
    "                    break\n",
    "            if que:\n",
    "                break\n",
    "\n",
    "        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        res = 0\n",
    "        while que:\n",
    "            res += 1\n",
    "            size = len(que)\n",
    "            for i in range(size):\n",
    "                curx, cury = que.popleft()\n",
    "                for dx, dy in directions:\n",
    "                    nx, ny = curx + dx, cury + dy\n",
    "                    if nx < 0 or nx >= n or ny < 0 or ny >= m or grid[nx][ny] == \"X\":continue\n",
    "                    if grid[nx][ny] == \"#\":\n",
    "                        return res \n",
    "                    que.append((nx, ny))\n",
    "                    grid[nx][ny] = \"X\"\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFood(self, grid: List[List[str]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = [[0] * n for _ in range(m)]\n",
    "        sx, sy = next([x, y] for x in range(m) for y in range(n) if grid[x][y] == '*')\n",
    "        visited[sx][sy] = 1\n",
    "        dir = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        dq = deque([[sx, sy, 0]])\n",
    "\n",
    "        def valid(i, j):\n",
    "            return 0 <= i < m and 0 <= j < n \n",
    "\n",
    "        while dq:\n",
    "            for _ in range(len(dq)):\n",
    "                x, y, d = dq.popleft()\n",
    "                if grid[x][y] == '#':\n",
    "                    return d \n",
    "                for dx, dy in dir:\n",
    "                    nx, ny = x + dx, y + dy \n",
    "                    if valid(nx, ny) and grid[nx][ny] != 'X' and visited[nx][ny] == 0:\n",
    "                        dq.append([nx, ny, d + 1])\n",
    "                        visited[nx][ny] = 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFood(self, grid: List[List[str]]) -> int:\n",
    "        \n",
    "        row,col = len(grid),len(grid[0])\n",
    "\n",
    "        visited = [[False]*col for _ in range(row)]\n",
    "\n",
    "        for r in range(row):\n",
    "            for c in range(col):\n",
    "                if grid[r][c]=='*':\n",
    "                    start=[r,c]\n",
    "                    break\n",
    "        \n",
    "        q = [start]\n",
    "        visited[start[0]][start[1]] = True\n",
    "        step = 0\n",
    "        #记忆化+BFS\n",
    "        while q:\n",
    "            cur_len = len(q)\n",
    "            step += 1\n",
    "            for _ in range(cur_len):\n",
    "                r,c = q.pop(0)\n",
    "                for dr,dc in [(-1,0),(0,1),(1,0),(0,-1)]:\n",
    "                    nr = r+dr\n",
    "                    nc = c+dc\n",
    "                    if 0<=nr < row and 0<=nc<col and visited[nr][nc]==False and grid[nr][nc] != 'X':\n",
    "                        if grid[nr][nc]=='#':\n",
    "                            return step\n",
    "                        visited[nr][nc]=True\n",
    "                        q.append([nr,nc])\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFood(self, grid: List[List[str]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        # find '*'\n",
    "        for startx in range(m):\n",
    "            flag = False\n",
    "            for starty in range(n):\n",
    "                if grid[startx][starty] == '*':\n",
    "                    flag = True\n",
    "                    break\n",
    "            if flag:\n",
    "                break\n",
    "      \n",
    "        vis = [[False]*n for _ in range(m)]\n",
    "\n",
    "        # BFS to search food\n",
    "        q = collections.deque([(startx, starty)])\n",
    "        vis[startx][starty] = True\n",
    "\n",
    "        step = 0\n",
    "        while q:\n",
    "            step += 1\n",
    "            length = len(q)\n",
    "            for _ in range(length):\n",
    "                sx, sy = q.popleft()\n",
    "                for x, y in ((sx+1,sy),(sx-1,sy),(sx,sy-1),(sx,sy+1)):\n",
    "                    if x < 0 or x >= m or y < 0 or y >= n or vis[x][y]:\n",
    "                        continue\n",
    "                    if grid[x][y] == '#':\n",
    "                        return step\n",
    "                    vis[x][y] = True\n",
    "                    if grid[x][y] == 'O':\n",
    "                        q.append((x,y))\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFood(self, grid: List[List[str]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        queue = deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '*':\n",
    "                    queue.append([i,j])\n",
    "                    break\n",
    "            if queue:\n",
    "                break\n",
    "        # print(queue)\n",
    "        ans = 0\n",
    "        while queue:\n",
    "            ans += 1\n",
    "            for _ in range(len(queue)):\n",
    "                x,y = queue.pop()\n",
    "                for i,j in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:\n",
    "                    if not(0<=i<m and 0<=j<n) or grid[i][j] == 'X':\n",
    "                        continue\n",
    "                    if grid[i][j] == '#':\n",
    "                        return ans\n",
    "                    grid[i][j] = 'X'\n",
    "                    queue.appendleft([i,j])\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFood(self, grid: List[List[str]]) -> int:\n",
    "\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        next_move = [[1, 0], [-1, 0], [0, 1], [0, -1]]\n",
    "        ans = []\n",
    "        que = collections.deque()\n",
    "        move = [0,0]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == \"*\":\n",
    "                    start_x, start_y = j, i\n",
    "                    break\n",
    "\n",
    "        que.append([start_y, start_x])\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        while(que):\n",
    "            ans += 1\n",
    "            length = len(que)\n",
    "            for _ in range(length):\n",
    "                i, j = que.pop()\n",
    "                for mv in next_move:\n",
    "                    move[0] = mv[0] + i\n",
    "                    move[1] = mv[1] + j\n",
    "                    if move[0] < 0 or move[0] >= n:\n",
    "                        continue\n",
    "                    \n",
    "                    if move[1] < 0 or move[1] >= m:\n",
    "                        continue\n",
    "\n",
    "                    if grid[move[0]][move[1]] == \"#\":\n",
    "                        return ans\n",
    "                    \n",
    "                    if grid[move[0]][move[1]] == \"X\":\n",
    "                        continue\n",
    "\n",
    "                    grid[move[0]][move[1]] = \"X\"\n",
    "                    que.appendleft(move[:])\n",
    "                    \n",
    "                \n",
    "        return -1\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFood(self, grid: List[List[str]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        directions = [[-1, 0], [1, 0], [0, 1], [0, -1]]\n",
    "        q = deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == \"*\":\n",
    "                    q.append((i, j))\n",
    "                    break\n",
    "            if q:\n",
    "                break\n",
    "\n",
    "        length = 0\n",
    "        while q:\n",
    "            length += 1\n",
    "            for _ in range(len(q)):\n",
    "                curr_x, curr_y = q.popleft()\n",
    "                for x, y in directions:\n",
    "                    nxt_x, nxt_y = curr_x + x, curr_y + y\n",
    "                    if not (0 <= nxt_x < m and 0 <= nxt_y < n) or grid[nxt_x][nxt_y] == \"X\":\n",
    "                        continue\n",
    "                    if grid[nxt_x][nxt_y] == \"#\":\n",
    "                        return length\n",
    "                    grid[nxt_x][nxt_y] = \"X\"\n",
    "                    q.append((nxt_x, nxt_y))\n",
    "            \n",
    "        return -1\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFood(self, grid: List[List[str]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        queue = deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '*':\n",
    "                    queue.append([i,j])\n",
    "                    break\n",
    "            if queue:\n",
    "                break\n",
    "        # print(queue)\n",
    "        ans = 0\n",
    "        while queue:\n",
    "            ans += 1\n",
    "            for _ in range(len(queue)):\n",
    "                x,y = queue.pop()\n",
    "                for i,j in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:\n",
    "                    if not(0<=i<m and 0<=j<n) or grid[i][j] == 'X':\n",
    "                        continue\n",
    "                    if grid[i][j] == '#':\n",
    "                        return ans\n",
    "                    grid[i][j] = 'X'\n",
    "                    queue.appendleft([i,j])\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFood(self, grid: List[List[str]]) -> int:\n",
    "\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        q = collections.deque()\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == \"*\":\n",
    "                    q.append((i, j))\n",
    "                    grid[i][j] = \"X\"\n",
    "        \n",
    "        step = 0\n",
    "        while q:\n",
    "            step += 1\n",
    "            lenth = len(q)\n",
    "            for _ in range(lenth):\n",
    "                i, j = q.popleft()\n",
    "                directions = ((0, 1), (0, -1), (1, 0), (-1, 0))\n",
    "                for direction in directions:\n",
    "                    x, y = i + direction[0], j + direction[1]\n",
    "                    if -1 < x < m and -1 < y < n:\n",
    "                        if grid[x][y] == \"#\":\n",
    "                            return step\n",
    "                        \n",
    "                        elif grid[x][y] == \"O\":\n",
    "                            grid[x][y] = \"X\"\n",
    "                            q.append((x, y))\n",
    "            \n",
    "        return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFood(self, grid: List[List[str]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        steps = 0\n",
    "        q = deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]=='*':\n",
    "                    q.append((i,j))\n",
    "                    break\n",
    "            else:\n",
    "                continue\n",
    "            break\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            for _ in range(size):\n",
    "                x,y = q.popleft()\n",
    "                for dx,dy in pairwise((-1,0,1,0,-1)):\n",
    "                    newx,newy = x+dx,y+dy\n",
    "                    if 0<=newx<m and 0<=newy<n:\n",
    "                        if grid[newx][newy]=='#':\n",
    "                            return steps+1\n",
    "                        if grid[newx][newy]=='O':\n",
    "                            q.append((newx,newy))\n",
    "                            grid[newx][newy]='1'\n",
    "            steps+=1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFood(self, grid: List[List[str]]) -> int:\n",
    "        row, col = len(grid), len(grid[0])\n",
    "        queue = deque()\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == '*':\n",
    "                    queue.append([i, j])\n",
    "                    break\n",
    "            if queue:\n",
    "                break\n",
    "\n",
    "        res = 0\n",
    "        dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        while queue:\n",
    "            res += 1\n",
    "            for i in range(len(queue)):\n",
    "                node = queue.pop()\n",
    "                for dir in dirs:\n",
    "                    r = node[0] + dir[0]\n",
    "                    c = node[1] + dir[1]\n",
    "                    if 0 <= r < row and 0 <= c < col and grid[r][c] != 'X':\n",
    "                        if grid[r][c] == '#':\n",
    "                            return res\n",
    "                        else:\n",
    "                            grid[r][c] = 'X'\n",
    "                            queue.appendleft([r, c])\n",
    "        return -1\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFood(self, grid: List[List[str]]) -> int:\n",
    "        q = []\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '*':\n",
    "                    q.append((i,j))\n",
    "                    break\n",
    "        dist = [[inf] * n for _ in range(m)]\n",
    "        dist[q[0][0]][q[0][1]] = 0\n",
    "\n",
    "        while q:\n",
    "            print(f'{q}')\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for x, y in tmp:\n",
    "                if grid[x][y] == '#':\n",
    "                    return dist[x][y]\n",
    "                for nx,ny in (x + 1,y),(x-1,y),(x,y+1),(x,y-1):\n",
    "                    if not (0<= nx < m and 0 <= ny <n): continue\n",
    "                    if grid[nx][ny] == 'X': continue\n",
    "                    # print(f'{(x,y), dist[x][y], dist[nx][ny]}')\n",
    "                    if dist[x][y] + 1 < dist[nx][ny]:\n",
    "                        dist[nx][ny] = dist[x][y] + 1\n",
    "                        q.append((nx,ny))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFood(self, grid: List[List[str]]) -> int:\n",
    "        m, n = len(grid),len(grid[0])\n",
    "        queue = deque()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '*':\n",
    "                    queue.append((i,j))\n",
    "                    break\n",
    "            if queue:\n",
    "                break\n",
    "        ans = 0\n",
    "\n",
    "        while queue:  \n",
    "            ans += 1        \n",
    "            print(queue)\n",
    "            for _ in range(len(queue)):\n",
    "                x,y = queue.pop()\n",
    "                for (x_,y_) in [(x+1,y),(x-1,y),(x,y-1),(x,y+1)]:\n",
    "                    if x_ not in range(0,m) or y_ not in range(0,n) or grid[x_][y_] == 'X':\n",
    "                        continue\n",
    "                    if grid[x_][y_] == '#':\n",
    "                        return ans\n",
    "                    grid[x_][y_] = 'X'\n",
    "                    queue.appendleft((x_,y_))\n",
    "                \n",
    "                \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFood(self, grid: List[List[str]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        q=[]\n",
    "        ans=[0,0]\n",
    "        dp=[[-1]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]=='#':\n",
    "                    q.append((i,j))\n",
    "                    dp[i][j]=0\n",
    "                elif grid[i][j]=='X':\n",
    "                    dp[i][j]=0\n",
    "                elif grid[i][j]=='*':\n",
    "                    ans=[i,j]\n",
    "        while q:\n",
    "            q,nq=[],q\n",
    "            for x,y in nq:\n",
    "                for nx,ny in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:\n",
    "                    if 0<=nx<m and 0<=ny<n and dp[nx][ny]==-1:\n",
    "                        dp[nx][ny]=dp[x][y]+1\n",
    "                        q.append((nx,ny))\n",
    "        return dp[ans[0]][ans[1]]\n",
    "\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFood(self, grid: List[List[str]]) -> int:\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        que = collections.deque()\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "\n",
    "                if grid[i][j] == \"*\":\n",
    "                    que.append((i,j))\n",
    "                    break\n",
    "            if que:\n",
    "                break\n",
    "\n",
    "        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        res = 0\n",
    "        while que:\n",
    "            res += 1\n",
    "            size = len(que)\n",
    "            for i in range(size):\n",
    "                curx, cury = que.popleft()\n",
    "                for dx, dy in directions:\n",
    "                    nx, ny = curx + dx, cury + dy\n",
    "                    if nx < 0 or nx >= n or ny < 0 or ny >= m or grid[nx][ny] == \"X\":continue\n",
    "                    if grid[nx][ny] == \"#\":\n",
    "                        return res \n",
    "                    que.append((nx, ny))\n",
    "                    grid[nx][ny] = \"X\"\n",
    "\n",
    "        return -1\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFood(self, grid: List[List[str]]) -> int:\n",
    "        row, col = len(grid), len(grid[0])\n",
    "        queue = deque()\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == '*':\n",
    "                    queue.append([i, j])\n",
    "                    break\n",
    "            if queue:\n",
    "                break\n",
    "\n",
    "        res = 0\n",
    "        dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        while queue:\n",
    "            res += 1\n",
    "            for i in range(len(queue)):\n",
    "                node = queue.pop()  # deque from the right side\n",
    "                for dir in dirs:\n",
    "                    r = node[0] + dir[0]\n",
    "                    c = node[1] + dir[1]\n",
    "                    if 0 <= r < row and 0 <= c < col and grid[r][c] != 'X':\n",
    "                        if grid[r][c] == '#':\n",
    "                            return res\n",
    "                        else:\n",
    "                            grid[r][c] = 'X'\n",
    "                            queue.appendleft([r, c])    #enque from the left side\n",
    "        return -1\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFood(self, grid: List[List[str]]) -> int:\n",
    "\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        next_move = [[1, 0], [-1, 0], [0, 1], [0, -1]]\n",
    "        ans = []\n",
    "        que = collections.deque()\n",
    "        move = [0,0]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == \"*\":\n",
    "                    start_x, start_y = j, i\n",
    "                    break\n",
    "\n",
    "        que.append([start_y, start_x])\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        while(que):\n",
    "            ans += 1\n",
    "            length = len(que)\n",
    "            print(que)\n",
    "            for _ in range(length):\n",
    "                i, j = que.pop()\n",
    "                for mv in next_move:\n",
    "                    move[0] = mv[0] + i\n",
    "                    move[1] = mv[1] + j\n",
    "                    if move[0] < 0 or move[0] >= n:\n",
    "                        continue\n",
    "                    \n",
    "                    if move[1] < 0 or move[1] >= m:\n",
    "                        continue\n",
    "\n",
    "                    if grid[move[0]][move[1]] == \"#\":\n",
    "                        return ans\n",
    "                    \n",
    "                    if grid[move[0]][move[1]] == \"X\":\n",
    "                        continue\n",
    "\n",
    "                    grid[move[0]][move[1]] = \"X\"\n",
    "                    que.appendleft(move[:])\n",
    "                    \n",
    "                \n",
    "        return -1\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFood(self, grid: List[List[str]]) -> int:\n",
    "\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        q = collections.deque()\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == \"*\":\n",
    "                    q.append((i, j))\n",
    "                    grid[i][j] = \"X\"\n",
    "        \n",
    "        step = 0\n",
    "        while q:\n",
    "            step += 1\n",
    "            lenth = len(q)\n",
    "            for _ in range(lenth):\n",
    "                i, j = q.popleft()\n",
    "                directions = ((0, 1), (0, -1), (1, 0), (-1, 0))\n",
    "                for direction in directions:\n",
    "                    x, y = i + direction[0], j + direction[1]\n",
    "                    if -1 < x < m and -1 < y < n:\n",
    "                        print(x, y, grid[x][y])\n",
    "                        if grid[x][y] == \"#\":\n",
    "                            return step\n",
    "                        \n",
    "                        elif grid[x][y] == \"O\":\n",
    "                            grid[x][y] = \"X\"\n",
    "                            q.append((x, y))\n",
    "            \n",
    "        return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFood(self, grid: List[List[str]]) -> int:\n",
    "      from collections import deque\n",
    "\n",
    "      m = len(grid)\n",
    "      n = len(grid[0])\n",
    "\n",
    "      queue = deque()\n",
    "\n",
    "      for i in range(m):\n",
    "        for j in range(n):\n",
    "          if grid[i][j] == \"*\":\n",
    "            queue.append((i, j))\n",
    "            visited = {(i, j): 0}\n",
    "            break\n",
    "        if queue:\n",
    "          break\n",
    "\n",
    "      steps = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "\n",
    "      while queue:\n",
    "        # print(queue)\n",
    "\n",
    "        x, y = queue.popleft()\n",
    "        depth = visited[(x, y)]\n",
    "\n",
    "        for dx, dy in steps:\n",
    "          nx = x + dx\n",
    "          ny = y + dy\n",
    "          if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] != \"X\":\n",
    "            if grid[nx][ny] == \"#\":\n",
    "              return depth + 1\n",
    "\n",
    "            if (nx, ny) in visited:\n",
    "              continue\n",
    "\n",
    "            visited[(nx, ny)] = depth + 1\n",
    "            queue.append((nx, ny))\n",
    "\n",
    "      return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFood(self, grid: List[List[str]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, x in enumerate(row):\n",
    "                if x == '*':\n",
    "                    q = [(i, j)]\n",
    "        vis = set(q)\n",
    "        ans = 0\n",
    "        while q:\n",
    "            nq = []\n",
    "            for i, j in q:\n",
    "                if grid[i][j] == '#':\n",
    "                    return ans\n",
    "                for x, y in (i+1, j), (i-1, j), (i, j+1), (i, j-1):\n",
    "                    if 0 <= x < m and 0 <= y < n  and grid[x][y] != 'X' and (x, y) not in vis:\n",
    "                        vis.add((x, y))\n",
    "                        nq.append((x, y))\n",
    "            ans += 1\n",
    "            q = nq\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFood(self, grid: List[List[str]]) -> int:\n",
    "        q = []\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '*':\n",
    "                    q.append((i,j))\n",
    "                    break\n",
    "        vis = set()\n",
    "        vis.add((q[0][0], q[0][1]))\n",
    "        d = 0\n",
    "        # print(f'{q},{vis}')\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for x, y in tmp:\n",
    "                if grid[x][y] == '#':\n",
    "                    return d\n",
    "                for nx, ny in (x + 1, y),(x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if not (0 <= nx < m and 0 <= ny < n): continue\n",
    "                    if (nx, ny) in vis or grid[nx][ny] == 'X': continue \n",
    "                    vis.add((nx, ny))\n",
    "                    q.append((nx,ny))\n",
    "            d += 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFood(self, grid: List[List[str]]) -> int:\n",
    "        start = (0,0)\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == \"*\":\n",
    "                    start = (i,j)\n",
    "                    break\n",
    "        queue = collections.deque()\n",
    "        queue.append(start)\n",
    "        visited = set()\n",
    "        visited.add(start)\n",
    "        depth = 1\n",
    "        vec = [(0,1),(0,-1),(-1,0),(1,0)]\n",
    "        while len(queue) > 0:\n",
    "            size = len(queue)\n",
    "            # print(queue, depth)\n",
    "            for _ in range(size):\n",
    "                x, y = queue.popleft()\n",
    "                for dx, dy in vec:\n",
    "                    new_x, new_y = x + dx, y + dy\n",
    "                    if new_x >= 0 and new_y >= 0 and new_x < len(grid) and new_y < len(grid[0]):\n",
    "                        if grid[new_x][new_y] == \"#\":\n",
    "                            return depth\n",
    "                        elif grid[new_x][new_y] == \"O\" and (new_x, new_y) not in visited:\n",
    "                            queue.append((new_x,new_y))\n",
    "                            visited.add(((new_x,new_y)))\n",
    "            depth += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def getFood(self, grid: List[List[str]]) -> int:\n",
    "        if not grid:\n",
    "            return -1\n",
    "        \n",
    "        rows, cols = len(grid), len(grid[0])\n",
    "        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "        \n",
    "        # Find the starting position\n",
    "        for r in range(rows):\n",
    "            for c in range(cols):\n",
    "                if grid[r][c] == '*':\n",
    "                    start = (r, c)\n",
    "                    break\n",
    "        \n",
    "        # BFS to find the shortest path to food\n",
    "        queue = deque([(start, 0)]) # Each element is ((r, c), steps)\n",
    "        visited = set()\n",
    "        visited.add(start)\n",
    "        \n",
    "        while queue:\n",
    "            (curr_r, curr_c), steps = queue.popleft()\n",
    "            \n",
    "            # Check if we found the food\n",
    "            if grid[curr_r][curr_c] == '#':\n",
    "                return steps\n",
    "            \n",
    "            # Check the neighbors\n",
    "            for dr, dc in directions:\n",
    "                new_r, new_c = curr_r + dr, curr_c + dc\n",
    "                if 0 <= new_r < rows and 0 <= new_c < cols and grid[new_r][new_c] != 'X' and (new_r, new_c) not in visited:\n",
    "                    visited.add((new_r, new_c))\n",
    "                    queue.append(((new_r, new_c), steps + 1))\n",
    "        \n",
    "        # If we've exhausted all possible paths and haven't found food\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFood(self, grid: List[List[str]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        start = None\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '*':\n",
    "                    start = (i, j)\n",
    "                    break\n",
    "            if start: break\n",
    "        q, s = [start], []\n",
    "        res, seen = 0, set(q)\n",
    "        while q:\n",
    "            while q:\n",
    "                i, j = q.pop()\n",
    "                if grid[i][j] == '#':\n",
    "                    return res\n",
    "                for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:\n",
    "                    if 0 <= x < m and 0 <= y < n and grid[x][y] in ['O', '#'] and (x, y) not in seen:\n",
    "                        seen.add((x, y))\n",
    "                        s.append((x, y))\n",
    "            q, s = s, q\n",
    "            res +=1\n",
    "        return -1\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFood(self, grid: List[List[str]]) -> int:\n",
    "        #当前层级位置\n",
    "        cur_node = {}\n",
    "        visited = {}\n",
    "        # 行\n",
    "        n = len(grid)\n",
    "        # 列\n",
    "        m = len(grid[0])\n",
    "        jump = 0\n",
    "        # 找到人的位置\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[i])):\n",
    "                if grid[i][j] == '*':\n",
    "                    cur_node[\"{}_{}\".format(i,j)] = \"\"\n",
    "        while cur_node != {}:\n",
    "            child_node = {}\n",
    "            for key in cur_node:\n",
    "                visited[key] = \"1\"\n",
    "                node_p = key.split(\"_\")\n",
    "                i = int(node_p[0])\n",
    "                j = int(node_p[1])\n",
    "                if grid[i][j] == '#':\n",
    "                    return jump\n",
    "                # 向上移动\n",
    "                if i > 0 and grid[i-1][j] != \"X\" and \"{}_{}\".format(i-1,j) not in visited and \"{}_{}\".format(i-1,j) not in child_node:\n",
    "                    child_node[\"{}_{}\".format(i-1,j)] = cur_node[key] + \"_top\"\n",
    "                if i + 1 < n and grid[i+1][j] != \"X\" and \"{}_{}\".format(i+1,j) not in visited and \"{}_{}\".format(i+1,j) not in child_node:\n",
    "                    child_node[\"{}_{}\".format(i + 1, j)] = cur_node[key] + \"_bottom\"\n",
    "                if j > 0 and grid[i][j-1] != \"X\" and \"{}_{}\".format(i,j-1) not in visited and \"{}_{}\".format(i,j-1) not in child_node:\n",
    "                    child_node[\"{}_{}\".format(i,j-1)] = cur_node[key] + \"_left\"\n",
    "                if j + 1 < m and grid[i][j+1] != \"X\" and \"{}_{}\".format(i,j+1) not in visited and \"{}_{}\".format(i,j+1) not in child_node:\n",
    "                    child_node[\"{}_{}\".format(i,j+1)] = cur_node[key] + \"_right\"\n",
    "            jump += 1\n",
    "            cur_node = child_node\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFood(self, grid: List[List[str]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        queue = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '*':\n",
    "                    queue.append([i, j, 0])\n",
    "                    break\n",
    "\n",
    "        visited = set()\n",
    "        visited.add((queue[0][0], queue[0][1]))\n",
    "        direction = [[0, 1], [1, 0], [-1, 0], [0, -1]]\n",
    "        while queue:\n",
    "            x, y, path = queue.pop(0)\n",
    "            for dx, dy in direction:\n",
    "                newx = x + dx\n",
    "                newy = y + dy\n",
    "                if 0 <= newx < m and 0 <= newy < n and (newx, newy) not in visited and grid[newx][newy] != 'X':\n",
    "                    if grid[newx][newy] == '#':\n",
    "                        return path + 1\n",
    "                    queue.append([newx, newy, path+1])\n",
    "                    visited.add((newx, newy))\n",
    "        return -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
